package cn.cnsuh.q733_floodFill;

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        int[][] imge = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
        int sr = 1;
        int sc = 1;
        int newColor = 2;
        int[][] ints = floodFill(imge, sr, sc, newColor);
        for (int i = 0; i < ints.length; i++) {
            for (int j = 0; j < ints[0].length; j++) {
                System.out.print(ints[i][j] + " ");
            }
            System.out.println();
        }
    }

    static int[] dx = {1, 0, 0, -1};
    static int[] dy = {0, 1, -1, 0};

    static int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int curColor = image[sr][sc];
        if (newColor == curColor) {
            return image;
        }
        int n = image.length;
        int m = image[0].length;
        Node start = new Node(sr, sc);
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(start);
        while (!queue.isEmpty()) {
            Node t = queue.poll();
            image[t.x][t.y] = newColor;
            for (int i = 0; i < 4; i++) {
                int xx = t.x + dx[i];
                int yy = t.y + dy[i];
                if (xx < 0 || xx >= n || yy < 0 || yy >= m) {
                    continue;
                }
                if (image[xx][yy] != curColor) {
                    continue;
                }

                queue.add(new Node(xx, yy));
            }

        }
        return image;

    }
}

class Node {
    int x;
    int y;

    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}